/// @tags: SAM
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

constexpr int MAXN = 2e5 + 5, SAMN = MAXN * 2, ST = 19;

int q, samcnt = 1;
int len[SAMN], link[SAMN], ch[SAMN][2];
int maxlen[MAXN], f[MAXN][ST], lg[MAXN];
char s[MAXN], t[MAXN];

inline void extend(int c) {
  static int lst = 1;
  int p = lst, np = lst = ++samcnt;
  len[np] = len[p] + 1;
  while (p && !ch[p][c]) ch[p][c] = np, p = link[p];
  if (p == 0) {
    link[np] = 1;
    return;
  }
  int q = ch[p][c];
  if (len[q] == len[p] + 1) {
    link[np] = q;
    return;
  }
  int nq = ++samcnt;
  ch[nq][0] = ch[q][0], ch[nq][1] = ch[q][1];
  len[nq] = len[p] + 1, link[nq] = link[q], link[q] = link[np] = nq;
  while (ch[p][c] == q) ch[p][c] = nq, p = link[p];
}

inline int query(int l, int r) {
  if (l > r) return 0;
  int k = lg[r - l + 1];
  return max(f[l][k], f[r - (1 << k) + 1][k]);
}

inline int find(int l, int r) {
  int pos = r + 1, L = l;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (mid - maxlen[mid] + 1 >= L)
      pos = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return pos;
}

inline void traverse(const char s[], int slen) {
  int cur = 1;
  for (int i = 1; i <= slen; ++i) {
    int c = s[i] - 'a';
    if (ch[cur][c])
      maxlen[i] = maxlen[i - 1] + 1, cur = ch[cur][c];
    else {
      while (cur != 0 && ch[cur][c] == 0) cur = link[cur];
      if (cur == 0)
        cur = 1;
      else
        maxlen[i] = len[cur] + 1, cur = ch[cur][c];
    }
  }
}

inline int main() {
  cin >> (s + 1) >> (t + 1);
  int slen = strlen(s + 1), tlen = strlen(t + 1);
  for (int i = 1; i <= tlen; ++i) extend(t[i] - 'a');
  traverse(s, slen);
  for (int i = 2; i <= slen; ++i) lg[i] = lg[i / 2] + 1;
  for (int i = 1; i <= slen; ++i) f[i][0] = maxlen[i];
  for (int j = 1; j < ST; ++j)
    for (int i = 1; i + (1 << j) - 1 <= slen; ++i)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
  cin >> q;
  for (int l, r, pos; q; --q) {
    cin >> l >> r;
    pos = find(l, r);
    cout << max(query(pos, r), pos - l) << '\n';
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P6640 [BJOI2020] 封印.in", "r", stdin);
  freopen("P6640 [BJOI2020] 封印.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
